package Year22_Month07.day03;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class 全排列2 {
    List<List<Integer>> resList = new LinkedList<>();
    List<Integer> list = new LinkedList<>();


    public List<List<Integer>> permuteUnique(int[] nums) {
        //用一个boolean数组来记录元素遍历过与否,因为boolean数组初始值全部是false
        boolean[] arr = new boolean[nums.length];
        Arrays.fill(arr,false);
        Arrays.sort(nums);
        backstracking(nums,arr);
        return resList;
    }

    public void backstracking(int[] nums,boolean[] arr){
        if(list.size() == nums.length){
            resList.add(new LinkedList<>(list));
        }

        for (int i = 0; i < nums.length; i++) {
            //这里就是对同一树层剪枝
            if(i > 0 && nums[i] == nums[i - 1] && arr[i - 1] == false){
                continue;
            }
            //这里开始对没有使用过的树枝开始进行操作
            if(arr[i] == false){
                arr[i] = true;//标记当前树枝已经使用过，不能重复使用
                list.add(nums[i]);
                backstracking(nums,arr);
                arr[i] = false;//回溯，表示使用完毕
                list.remove(list.size() - 1);//回溯，说明同一树层nums[i]使用过
            }
        }
    }
}
